/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 * https://leetcode-cn.com/problems/longest-harmonious-subsequence/
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<int>& arr, string const str){
    vector<int>::iterator it;
    cout << str << ": ";
    for(it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}
// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i=0; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}


// 注意子序列不连续
class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        // visit_arr(nums, "sorted: ");
        int ans = 0;
        int minIndex=0, bigOneIndex=0;
        for(int i=0; i<nums.size(); ++i) {
            
            // cout <<"ans: " <<  ans << " i: "<< i  << " nums[i]:"<< nums[i] << " minIndex: "<< minIndex << endl;
            if(nums[i] - nums[minIndex] > 1){
                if ( nums[i-1] - nums[minIndex] == 1){
                    ans = ans > (i-minIndex) ? ans : (i-minIndex);
                }
                minIndex=bigOneIndex;
                bigOneIndex = 0;
            }
            if(nums[i] > nums[minIndex] && bigOneIndex == 0){
                bigOneIndex = i;
                // cout << "bigOneIndex: "<< bigOneIndex << endl;
            }
        }

        if(nums[nums.size() - 1] - nums[minIndex] ==1)
        {
            ans = ans > nums.size()-minIndex ? ans : nums.size()-minIndex;
        }
        // cout << minIndex << endl;
        return ans;
    }
};

int main(int argc, const char** argv) {
    Solution solu = Solution();
    // vector<int> nums = {1,3,2,2,5,2,3,7}; // 5
    // vector<int> nums = {1,2,2,1}; // 4
    // vector<int> nums = {1,3,5,7,9,11,13,15,17};  // 0
    // vector<int> nums = {1,2,2,3,4,5,1,1,1,1};  // 7
    vector<int> nums = {3,2,2,3,2,1,3,3,3,-2,0,3,2,1,0,3,1,0,1,3,0,3,3};  // 14
    cout << solu.findLHS(nums) << endl;

    return 0;
}